//题目:
// 集团里有 n 名员工，他们可以完成各种各样的工作创造利润。
// 第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。
// 工作的任何至少产生 minProfit 利润的子集称为 盈利计划 。并且工作的成员总数最多为 n 。
// 有多少种计划可以选择？因为答案很大，所以 返回结果模 10^9 + 7 的值。

// 示例 1：
// 输入：n = 5, minProfit = 3, group = [2,2], profit = [2,3]
// 输出：2
// 解释：至少产生 3 的利润，该集团可以完成工作 0 和工作 1 ，或仅完成工作 1 。
// 总的来说，有两种计划。

// 示例 2：
// 输入：n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
// 输出：7
// 解释：至少产生 5 的利润，只要完成其中一种工作就行，所以该集团可以完成任何工作。
// 有 7 种可能的计划：(0)，(1)，(2)，(0,1)，(0,2)，(1,2)，以及 (0,1,2) 。
#include<iostream>
#include<cstring>
#include<vector>

using namespace std;
//代码
class Solution 
{
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) 
    {
        int MOD=1e9+7;
        //二维费用的01背包问题
        // // 1.创建dp表————dp[i][j][k]表示：选到第i中工作，用到的成员数不超过j，利润不小于k时，的最大计划方案数
        // int sz=group.size();
        // vector<vector<vector<int>>> dp(sz+1,vector<vector<int>>(n+1,vector<int>(minProfit+1)));
        // //2.初始化
        // for(int k=0;k<=minProfit;k++)
        //     for(int j=0;j<=n;j++)
        //         if(k==0) dp[0][j][k]=1;
        // //3.填表————动态转移方程 dp[i][j][k]=dp[i-1][j][k] + dp[i-1][j-group[i]][k-profit[i]];
        // for(int i=1;i<=sz;i++)
        // {
        //     for(int j=0;j<=n;j++)
        //     {
        //         for(int k=0;k<=minProfit;k++)
        //         {
        //             dp[i][j][k]=dp[i-1][j][k]%MOD;
        //             if(j-group[i-1]>=0) 
        //             {
        //                 if(profit[i-1]>k)
        //                     dp[i][j][k]+=dp[i-1][j-group[i-1]][0]%MOD;
        //                 else 
        //                     dp[i][j][k]+=dp[i-1][j-group[i-1]][k-profit[i-1]]%MOD;
        //             }                     
        //         }
        //     }
        // }
        // //4.确定返回值
        // return dp[sz][n][minProfit]%MOD;

        //空间优化
        //1.创建dp表————dp[i][j][k]表示：选到第i中工作，用到的成员数不超过j，利润不小于k时，的最大计划方案数
        int sz=group.size();
        vector<vector<int>> dp(n+1,vector<int>(minProfit+1));
        //2.初始化
        for(int j=0;j<=n;j++)
            dp[j][0]=1;
        //3.填表————动态转移方程 dp[i][j][k]=dp[i-1][j][k] + dp[i-1][j-group[i]][k-profit[i]];
        for(int i=1;i<=sz;i++)
        {
            for(int j=n;j>=group[i-1];j--)
            {
                for(int k=minProfit;k>=0;k--)
                {
                    if(profit[i-1]>k)
                        (dp[j][k]+=dp[j-group[i-1]][0])%=MOD;
                    else 
                        (dp[j][k]+=dp[j-group[i-1]][k-profit[i-1]])%=MOD;
                }
            }
        }
        //4.确定返回值
        return (dp[n][minProfit])%MOD;
    }
};